{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bioinformatics Algorithm\n",
    "\n",
    "## 过程化考核3: Heuristic Algorithm\n",
    "\n",
    "> Last Modified Time 2019-09-16 16:30 By ZeFengZhu\n",
    "\n",
    "### 问题描述\n",
    "\n",
    "简述启发式算法并给出优缺点及适用场景\n",
    "\n",
    "### 基础概念\n",
    "\n",
    "> [Authors: Vincent Kenny, Matthew Nathal, and Spencer Saldana (ChE 345 Spring 2014)](https://optimization.mccormick.northwestern.edu/index.php/Heuristic_algorithms \"Link\")\n",
    "\n",
    "> https://www.verywellmind.com/what-is-a-heuristic-2795235\n",
    "\n",
    "#### 特征\n",
    "启发式算法旨在通过牺牲速度的最优性(optimality)，准确性(accuracy)，精确性(precision)或完整性(completeness)来比传统方法更快，更有效地解决问题。\n",
    "\n",
    "#### 用途\n",
    "* 启发式算法通常用于解决NP完全问题(一类决策问题)\n",
    "* 在这些问题中，尽管可以提供给定的解决方案，但没有已知的有效方法可以快速，准确地找到解决方案\n",
    "* 启发式算法可以单独产生一个解决方案，也可以用来提供良好的基线(baseline)，并辅以优化算法\n",
    "* 当近似解足够且精确解必然在计算上昂贵时，最常使用启发式算法\n",
    "\n",
    "#### 描述\n",
    "启发式解决问题是一种非正式的、直观的、推测性的过程，在某些情况下会可以解决问题，但在其他情况下不会。应用启发式的结果是不可预测的，这意味着该策略可能比使用非启发式算法更有效，也可能不如使用非启发式算法有效。\n",
    "\n",
    "启发式是一种心理捷径，使人们能够快速有效地解决问题并做出判断。这些经验法则可以缩短决策时间，使人们能够在不停下来思考下一步行动的情况下发挥作用。启发式方法在许多情况下很有用，但它们也可能导致认知偏差。\n",
    "\n",
    "\n",
    "#### Advantages总结\n",
    "* 减少工作量：根据此理论，人们将启发式方法用作一种认知惰性。启发式方法减少了做出选择和决策所需的精力。\n",
    "* 属性替换：其他理论建议人们用简单但相关的问题代替较复杂和困难的问题。\n",
    "* 快速而节俭：还有其他理论认为，启发式方法实际上比有偏见更准确。换句话说，我们使用启发式方法是因为它们快速且通常是正确的\n",
    "\n",
    "#### Disadvantages总结\n",
    "虽然启发式方法可以加快我们的问题和决策过程的速度，但它们可能会引入错误。\n",
    "\n",
    "* 仅仅因为某件事在过去起作用并不意味着它会再次起作用，而依靠现有的启发式方法可能会使很难看到替代解决方案或提出新的想法\n",
    "* 启发式方法可能导致关于常见事物如何发生以及某些事物可能具有代表性的错误判断。\n",
    "* 启发式方法也可能会加深刻板印象和偏见。由于人们使用思维捷径对人们进行分类和分类，因此他们经常忽略更多相关信息，并创建与现实不符的刻板印象分类\n",
    "\n",
    "### 算法示例\n",
    "* 集群智能 (Swarm Intelligence)\n",
    "* 禁忌搜索 (Tabu Search)\n",
    "* 模拟退火 (Simulated Annealing)\n",
    "* 遗传算法 (Genetic Algorithms)\n",
    "* 人工神经网络 (Artificial Neural Networks)\n",
    "* 支持向量机 (Support Vector Machines)\n",
    "\n",
    "### 课程中的相关算法\n",
    "1. Boyer-Moore 子字符串查找算法\n",
    "2. BLAST相似序列搜索(构建HSP并打分设定阈值即为启发式思想)\n",
    "3. Clustal系列 多序列比对(根据距离构建进化树即为启发式思想)\n",
    "4. 获取共有序列(consensus sequence)\n",
    "5. Motif发现\n",
    "\n",
    "#### About Motif发现\n",
    "1. 优先依据前两条序列确定一个较为合适的motif，对该对序列的motif起始位置进行遍历，得出所有组合中最佳的\n",
    "2. 然后再遍历剩余的序列，依次找出拟定的motif在该次比对中的最优起始位置\n",
    "3. 最后返回所有序列上的motif起始位置\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
